package other;

public class integerBreak_343 {

    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;
        //0和1无法拆分
        for(int i=2;i <= n;i++){
            for(int j = 1 ; j < i -1 ;j++){    //所有情况的 dp[i] 比大小  ，遍历到 j = i -2 即可 ，j=i-1 在j=1时就有了
                //拆分情况，拆出来一个j，后续的通过dp自己拆, j 不用拆即可
                //如，j 为4时，若进行拆分为2*2，已经包含在之前 j=2时，dp[i-2]进行的情况内
                dp[i] = Math.max(dp[i] ,Math.max(j *( i - j ) , j * dp[ i - j ]));
            }
        }
        return dp[n];
    }


    public static void main(String[] args) {

    }
}
